{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Number of Weeks for Which You Can Work"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numberOfWeeks"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #你可以工作的最大周数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你&nbsp;<code>n</code> 个项目，编号从 <code>0</code> 到 <code>n - 1</code> 。同时给你一个整数数组 <code>milestones</code> ，其中每个 <code>milestones[i]</code> 表示第 <code>i</code> 个项目中的阶段任务数量。</p>\n",
    "\n",
    "<p>你可以按下面两个规则参与项目中的工作：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>每周，你将会完成 <strong>某一个</strong> 项目中的 <strong>恰好一个</strong>&nbsp;阶段任务。你每周都 <strong>必须</strong> 工作。</li>\n",
    "\t<li>在 <strong>连续的</strong> 两周中，你 <strong>不能</strong> 参与并完成同一个项目中的两个阶段任务。</li>\n",
    "</ul>\n",
    "\n",
    "<p>一旦所有项目中的全部阶段任务都完成，或者仅剩余一个阶段任务都会导致你违反上面的规则，那么你将&nbsp;<strong>停止工作</strong> 。注意，由于这些条件的限制，你可能无法完成所有阶段任务。</p>\n",
    "\n",
    "<p>返回在不违反上面规则的情况下你&nbsp;<strong>最多</strong>&nbsp;能工作多少周。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>milestones = [1,2,3]\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>一种可能的情形是：\n",
    "​​​​- 第 1 周，你参与并完成项目 0 中的一个阶段任务。\n",
    "- 第 2 周，你参与并完成项目 2 中的一个阶段任务。\n",
    "- 第 3 周，你参与并完成项目 1 中的一个阶段任务。\n",
    "- 第 4 周，你参与并完成项目 2 中的一个阶段任务。\n",
    "- 第 5 周，你参与并完成项目 1 中的一个阶段任务。\n",
    "- 第 6 周，你参与并完成项目 2 中的一个阶段任务。\n",
    "总周数是 6 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>milestones = [5,2,1]\n",
    "<strong>输出：</strong>7\n",
    "<strong>解释：</strong>一种可能的情形是：\n",
    "- 第 1 周，你参与并完成项目 0 中的一个阶段任务。\n",
    "- 第 2 周，你参与并完成项目 1 中的一个阶段任务。\n",
    "- 第 3 周，你参与并完成项目 0 中的一个阶段任务。\n",
    "- 第 4 周，你参与并完成项目 1 中的一个阶段任务。\n",
    "- 第 5 周，你参与并完成项目 0 中的一个阶段任务。\n",
    "- 第 6 周，你参与并完成项目 2 中的一个阶段任务。\n",
    "- 第 7 周，你参与并完成项目 0 中的一个阶段任务。\n",
    "总周数是 7 。\n",
    "注意，你不能在第 8 周参与完成项目 0 中的最后一个阶段任务，因为这会违反规则。\n",
    "因此，项目 0 中会有一个阶段任务维持未完成状态。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == milestones.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= milestones[i] &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-number-of-weeks-for-which-you-can-work](https://leetcode.cn/problems/maximum-number-of-weeks-for-which-you-can-work/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-number-of-weeks-for-which-you-can-work](https://leetcode.cn/problems/maximum-number-of-weeks-for-which-you-can-work/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3]', '[5,2,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeeks(self, milestones: List[int]) -> int:\n",
    "        maxTask = max(milestones)\n",
    "        maxIndex = milestones.index(maxTask)\n",
    "        total = sum(milestones[:maxIndex]+milestones[maxIndex+1:])\n",
    "        return total * 2 +1 if maxTask > total else maxTask + total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeeks(self, milestones: List[int]) -> int:\n",
    "        l = max(milestones)\n",
    "        s = sum(milestones)\n",
    "        r = s - l\n",
    "        if l > r:\n",
    "            return r * 2 + 1\n",
    "        else:\n",
    "            return l + r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeeks(self, milestones: List[int]) -> int:\n",
    "        maxTask = max(milestones)\n",
    "        maxIndex = milestones.index(maxTask)\n",
    "        total = sum(milestones[:maxIndex]+milestones[maxIndex+1:])\n",
    "        return total * 2 +1 if maxTask > total else maxTask + total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeeks(self, milestones: List[int]) -> int:\n",
    "        max_milestone = max(milestones)  # 最多阶段任务的项目\n",
    "        sum_milestones = sum(milestones)  # 所有项目的阶段任务总数\n",
    "        \n",
    "        # 如果所有其他项目的阶段任务数加起来大于或等于 max_milestone，\n",
    "        # 那么你可以完成所有阶段任务。\n",
    "        if sum_milestones - max_milestone >= max_milestone:\n",
    "            return sum_milestones\n",
    "        \n",
    "        # 否则，你需要确保每两周至少完成一个 max_milestone 项目的阶段任务\n",
    "        return 2 * (sum_milestones - max_milestone) + 1\n",
    "\n",
    "# 测试\n",
    "print(Solution().numberOfWeeks([1, 2, 3]))  # 应该输出 6\n",
    "print(Solution().numberOfWeeks([5, 2, 1]))  # 应该输出 7\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def numberOfWeeks(self, milestones: List[int]) -> int:\n",
    "        longest = max(milestones)\n",
    "        rest = sum(milestones) - longest\n",
    "        if longest > rest + 1:\n",
    "            return 2 * rest + 1\n",
    "        else:\n",
    "            return longest + rest"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeeks(self, milestones: List[int]):\n",
    "        # 耗时最长工作所需周数\n",
    "        longest = max(milestones)\n",
    "        # 其余工作共计所需周数\n",
    "        rest = sum(milestones) - longest\n",
    "        if longest > rest + 1:\n",
    "            # 此时无法完成所耗时最长的工作\n",
    "            return rest * 2 + 1\n",
    "        else:\n",
    "            # 此时可以完成所有工作\n",
    "            return longest + rest\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeeks(self, milestones: List[int]) -> int:\n",
    "        mx = max(milestones)\n",
    "        s = sum(milestones)\n",
    "        if mx > s - mx + 1:\n",
    "            return (s - mx) * 2 + 1\n",
    "        \n",
    "        return s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeeks(self, mt: List[int]) -> int:\n",
    "        mx = max(mt)\n",
    "        rem = sum(mt) - mx + 1\n",
    "        if mx <= rem: return rem + mx - 1\n",
    "        return 2 * rem - 1\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "        贪心(插空法)\n",
    "    '''\n",
    "    def numberOfWeeks(self, a: List[int]) -> int:\n",
    "        s = sum(a)\n",
    "        mx = max(a)\n",
    "        # 1.如果最大的任务数量 小于 其他任务数量的总和 那么这个最大的任务一定能全部完成\n",
    "        # 2.剩下一个任务无法完成 那么这个任务数量最多的 它最后对答案贡献是1\n",
    "        if mx > s - mx:\n",
    "            return 2 * (s - mx) + 1\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeeks(self, milestones: List[int]) -> int:\n",
    "        longest = max(milestones)\n",
    "        rest = sum(milestones) - longest\n",
    "        if longest > rest + 1:\n",
    "            return 2 * rest + 1\n",
    "        else:\n",
    "            return longest + rest"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeeks(self, milestones: List[int]) -> int:\n",
    "        m = max(milestones)\n",
    "        s = sum(milestones)\n",
    "        left = s - m\n",
    "        return s - m + min(s - m + 1, m)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeeks(self, milestones: List[int]):\n",
    "        max_week = max(milestones)\n",
    "        remain = sum(milestones) - max_week\n",
    "        res = 0\n",
    "        res = remain * 2 + 1 if max_week > remain + 1 else remain + max_week\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeeks(self, milestones: List[int]) -> int:\n",
    "        longest = max(milestones)\n",
    "        rest = sum(milestones) - longest\n",
    "        if longest > rest+1:\n",
    "            return rest*2+1\n",
    "        else:\n",
    "            return longest+rest"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeeks(self, milestones: List[int]) -> int:\n",
    "        l = len(milestones)\n",
    "        if l == 1:\n",
    "            return 1\n",
    "        milestones.sort(reverse=True)\n",
    "        target = sum(milestones) // 2\n",
    "        if milestones[0] > target:\n",
    "            return (sum(milestones) - milestones[0]) * 2 + 1\n",
    "        return sum(milestones)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeeks(self, milestones: List[int]) -> int:\n",
    "        s = sum(milestones)\n",
    "        maximum = max(milestones)\n",
    "        if maximum <= s - maximum:\n",
    "            return s\n",
    "        else:\n",
    "            return 2 * (s-maximum) + 1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeeks(self, milestones: List[int]) -> int:\n",
    "        ma = max(milestones)\n",
    "        t = sum(milestones)\n",
    "        if ma > t - ma + 1:\n",
    "            return (t - ma) * 2 + 1\n",
    "\n",
    "        return t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeeks(self, milestones: List[int]) -> int:\n",
    "        s = sum(milestones)\n",
    "        mx = max(milestones)\n",
    "        return s if s - mx >= mx - 1 else 2 * (s - mx) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeeks(self, milestones: List[int]) -> int:\n",
    "        return min(sum(milestones),2*(sum(milestones)-max(milestones))+1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeeks(self, milestones: List[int]) -> int:\n",
    "        l = len(milestones)\n",
    "        if l == 1:\n",
    "            return 1\n",
    "        max_work = max(milestones)\n",
    "        all_work = sum(milestones)\n",
    "        target = all_work // 2\n",
    "        if max_work > target:\n",
    "            return (all_work - max_work) * 2 + 1\n",
    "        return all_work\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeeks(self, milestones: List[int]) -> int:\n",
    "        # s=C0-Cn-2, mx=Cn-1\n",
    "        # s==mx, s==mx+1, s==mx-1 --> ans=s+mx\n",
    "        # s<mx-1 --> ans=2*s+1\n",
    "        # s>mx+1 --> ans\n",
    "        mx = max(milestones)\n",
    "        s = sum(milestones)\n",
    "        s -= mx\n",
    "        if s < mx:\n",
    "            return 2 * s + 1\n",
    "        return mx + s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeeks(self, milestones: List[int]) -> int:\n",
    "        return sum(milestones) if max(milestones)<=(sum(milestones)-max(milestones)+1) else (sum(milestones)-max(milestones))*2+1\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeeks(self, milestones: List[int]) -> int:\n",
    "        max_ = max(milestones)\n",
    "        sum_ = sum(milestones)\n",
    "        if max_ - (sum_-max_) >=2:\n",
    "            return 2*(sum_-max_)+1\n",
    "        return sum_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeeks(self, milestones: List[int]) -> int:\n",
    "        mx=max(milestones)\n",
    "        s=sum(milestones)\n",
    "        if s-mx>=mx:\n",
    "            return s\n",
    "        else:\n",
    "            x=s-mx\n",
    "            return x*2+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeeks(self, milestones: List[int]) -> int:\n",
    "        tmp_max = 0\n",
    "        total = 0\n",
    "        for milestone in milestones:\n",
    "            if milestone > tmp_max:\n",
    "                tmp_max = milestone\n",
    "            total += milestone\n",
    "        res = 0\n",
    "        if tmp_max > total - tmp_max:\n",
    "            res = (total - tmp_max) * 2 + 1\n",
    "        else:\n",
    "            res = total\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeeks(self, milestones: List[int]) -> int:\n",
    "        milestones.sort()\n",
    "        n=len(milestones)\n",
    "        if sum(milestones[0:n-1])+1<milestones[-1]:\n",
    "            return sum(milestones[0:n-1])*2+1\n",
    "        else:\n",
    "            return sum(milestones)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeeks(self, milestones: List[int]) -> int:\n",
    "        s = sum(milestones)\n",
    "        max_n = max(milestones)\n",
    "\n",
    "        if max_n > s - max_n + 1:\n",
    "            return s - max_n + s - max_n + 1\n",
    "        \n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeeks(self, milestones: List[int]):\n",
    "        max_week = max(milestones)\n",
    "        remain = sum(milestones) - max_week\n",
    "        return remain * 2 + 1 if max_week > remain + 1 else remain + max_week"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeeks(self, milestones: List[int]):\n",
    "        # 耗时最长工作所需周数\n",
    "        longest = max(milestones)\n",
    "        # 其余工作共计所需周数\n",
    "        rest = sum(milestones) - longest\n",
    "        if longest > rest + 1:\n",
    "            # 此时无法完成所耗时最长的工作\n",
    "            return rest * 2 + 1\n",
    "        else:\n",
    "            # 此时可以完成所有工作\n",
    "            return longest + rest\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeeks(self, milestones: List[int]) -> int:\n",
    "        s = mx = 0\n",
    "        for x in milestones:\n",
    "            s += x\n",
    "            mx = max(mx, x)\n",
    "        s -= mx\n",
    "        if mx > s + 1:\n",
    "            return 2 * s + 1\n",
    "        else:\n",
    "            return s + mx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeeks(self, milestones: List[int]) -> int:  \n",
    "        ma=max(milestones)\n",
    "        su=sum(milestones)\n",
    "        other=su-ma\n",
    "        if other+1<ma:\n",
    "            return 2*other+1\n",
    "        else:\n",
    "            return su"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeeks(self, milestones: List[int]) -> int:\n",
    "        #求不连续排相同数字的最大长度\n",
    "        if len(milestones) == 1:\n",
    "            return 1\n",
    "        milestones.sort()\n",
    "        total = sum(milestones)\n",
    "        p_max = milestones[-1]\n",
    "        subsum = total - p_max\n",
    "        # 分类讨论\n",
    "        if subsum < p_max:\n",
    "            res = 2 * subsum + 1\n",
    "        elif subsum == p_max:\n",
    "            res = 2 * subsum\n",
    "        elif subsum > p_max:\n",
    "            res = total\n",
    "\n",
    "        return res\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeeks(self, milestones: List[int]) -> int:\n",
    "        max_m = max(milestones)\n",
    "        res = sum(milestones)-max_m\n",
    "        if max_m > res+1:\n",
    "            return 2*res+1\n",
    "        else:\n",
    "            return max_m+res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeeks(self, milestones: List[int]) -> int:\n",
    "        mx = max(milestones)\n",
    "        su = sum(milestones)\n",
    "        return su if mx * 2 <= su else 2 * (su - mx) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeeks(self, milestones: List[int]) -> int:\n",
    "        a=max(milestones)\n",
    "        b=sum(milestones)\n",
    "        if 2*a<b+1:\n",
    "            return b\n",
    "        else:\n",
    "            return 2*(b-a)+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeeks(self, milestones: List[int]):\n",
    "        # 耗时最长工作所需周数\n",
    "        longest = max(milestones)\n",
    "        # 其余工作共计所需周数\n",
    "        rest = sum(milestones) - longest\n",
    "        if longest > rest + 1:\n",
    "            # 此时无法完成所耗时最长的工作\n",
    "            return rest * 2 + 1\n",
    "        else:\n",
    "            # 此时可以完成所有工作\n",
    "            return longest + rest"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def numberOfWeeks(self, milestones: List[int]) -> int:\r\n",
    "        ans = sum(milestones)\r\n",
    "        val = max(milestones)\r\n",
    "        if val > ans - val:\r\n",
    "            ans -= val - min(val, ans-val+1)\r\n",
    "        return ans\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeeks(self, nums: List[int]) -> int:\n",
    "        # 贪心考虑最大元素\n",
    "        mx = max(nums)\n",
    "        s = sum(nums)\n",
    "        # 最大元素*2 > 总数, 不能完全消去, 否则可以完全消去\n",
    "        if mx * 2 > s:\n",
    "            return (s - mx) *2 + 1\n",
    "        else:\n",
    "            return s\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeeks(self, milestones: List[int]) -> int:\n",
    "        mx = max(milestones)\n",
    "        s = sum(milestones)\n",
    "        if mx <= s - mx + 1:\n",
    "            return s\n",
    "        return 2 * (s - mx) + 1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeeks(self, milestones: List[int]) -> int:\n",
    "        m = max(milestones)\n",
    "        s = sum(milestones)\n",
    "        if s-m+1 >= m:\n",
    "            return s\n",
    "        else:\n",
    "            return s-m+1+s-m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeeks(self, m: List[int]) -> int:\n",
    "        m.sort()\n",
    "        total = sum(m)\n",
    "        if total < 2 * m[-1]:\n",
    "            return 2 * (total - m[-1]) + 1\n",
    "        else:\n",
    "            return total\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeeks(self, milestones: List[int]) -> int:\n",
    "        # 贪心\n",
    "        longst = max(milestones)\n",
    "        res = sum(milestones) - longst\n",
    "        if longst > res+1:\n",
    "            return 2*res+1\n",
    "        else:\n",
    "            return longst + res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeeks(self, milestones: List[int]) -> int:\n",
    "        milestones.sort()\n",
    "        sm = sum(milestones[:-1])\n",
    "        if sm < milestones[-1]:\n",
    "            return 2 * sm + 1\n",
    "        return sum(milestones)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeeks(self, milestones: List[int]) -> int:\n",
    "        a = max(milestones)\n",
    "        b = sum(milestones)-a\n",
    "        if a>b+1:\n",
    "            return 2*b+1\n",
    "        else:\n",
    "            return a+b\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeeks(self, milestones: List[int]) -> int:\n",
    "        n = len(milestones)\n",
    "        mx = max(milestones)\n",
    "        res = sum(milestones) - mx\n",
    "        if mx > res + 1:\n",
    "            return 2 * res + 1\n",
    "        return sum(milestones)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeeks(self, milestones: List[int]) -> int:\n",
    "        s, mx = sum(milestones), max(milestones)\n",
    "        if mx * 2 <= s:\n",
    "            return s\n",
    "        elif mx * 2 > s:\n",
    "            return 2 * (s - mx) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeeks(self, milestones: List[int]) -> int:\n",
    "        total = sum(milestones)\n",
    "        maxx = max(milestones)\n",
    "        lift = total - maxx\n",
    "        if maxx > lift:\n",
    "            return 2 * lift + 1\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeeks(self, milestones: List[int]) -> int:\n",
    "        longest = max(milestones)\n",
    "        rest = sum(milestones) - longest\n",
    "        if longest>rest+1:\n",
    "            return 2*rest + 1\n",
    "        return longest + rest"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeeks(self, milestones: List[int]) -> int:\n",
    "        if max(milestones) > sum(milestones) // 2:\n",
    "            return (sum(milestones) - max(milestones)) * 2 + 1\n",
    "        return sum(milestones)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeeks(self, milestones: List[int]) -> int:\n",
    "        # summ = sum(milestones)\n",
    "        # t = max(milestones)\n",
    "        # if t<=summ//2:return summ\n",
    "        # return 2*(summ-t)+1\n",
    "        maxx,summ = 0,0\n",
    "        for x in milestones:\n",
    "            summ+=x\n",
    "            maxx = max(maxx,x)\n",
    "        if maxx*2<=summ:return summ\n",
    "        return 2*(summ-maxx)+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeeks(self, milestones: List[int]) -> int:\n",
    "        mx = max(milestones)\n",
    "        rest = sum(milestones) - mx\n",
    "        if mx > rest:\n",
    "            return rest * 2 + 1\n",
    "        else:\n",
    "            return (mx + rest)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeeks(self, milestones: List[int]):\n",
    "        max_week = max(milestones)\n",
    "        remain = sum(milestones) - max_week\n",
    "        return remain * 2 + 1 if max_week > remain + 1 else remain + max_week"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeeks(self, milestones: List[int]):\n",
    "        max_week = max(milestones)\n",
    "        remain = sum(milestones) - max_week\n",
    "        return remain * 2 + 1 if max_week > remain + 1 else remain + max_week"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeeks(self, milestones: List[int]) -> int:\n",
    "        s = sum(milestones)\n",
    "        ceil = max(milestones)\n",
    "        if s - ceil >= ceil-1:\n",
    "            return s\n",
    "        return min(s, 2*(s-ceil)+1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeeks(self, milestones: List[int]) -> int:\n",
    "        S = sum(milestones)\n",
    "        m = max(milestones)\n",
    "        if S >= 2 * m:\n",
    "            return S\n",
    "        return (S - m) * 2 + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeeks(self, milestones: List[int]) -> int:\n",
    "        _max = max(milestones)\n",
    "        _sum = sum(milestones) - _max \n",
    "        if _sum + 1 < _max:\n",
    "            return _sum * 2 + 1\n",
    "        else:\n",
    "            return _max + _sum "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeeks(self, milestones: List[int]) -> int:\n",
    "        return min(sum(milestones), (sum(milestones) - max(milestones)) * 2 + 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeeks(self, milestones: List[int]):\n",
    "        # 耗时最长工作所需周数\n",
    "        longest = max(milestones)\n",
    "        # 其余工作共计所需周数\n",
    "        rest = sum(milestones) - longest\n",
    "        if longest > rest + 1:\n",
    "            # 此时无法完成所耗时最长的工作\n",
    "            return rest * 2 + 1\n",
    "        else:\n",
    "            # 此时可以完成所有工作\n",
    "            return longest + rest\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWeeks(self, milestones: List[int]) -> int:\n",
    "        milestones.sort()\n",
    "        ans = sum(milestones[:-1])\n",
    "        return ans + min(ans+1, milestones[-1])"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
